#include <algorithm>
#include <map>
#include <vector>
using namespace std;

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
		map<int, vector<int>> num2id;
		for (int i=0; i<nums.size(); i++)
		{
			num2id[nums[i]].push_back(i);
		}


		sort(nums.begin(), nums.end());

		int head = 0;
		int tail = nums.size() - 1;
		vector<int> res;
		while (true)
		{
			if (nums[head] + nums[tail] == target)
			{
				res.push_back(num2id[nums[head]][0]);
				if (nums[head] == nums[tail])
					res.push_back(num2id[nums[head]][1]);
				else
					res.push_back(num2id[nums[tail]][0]);
				break;
			}
			else if (nums[head] + nums[tail] < target)
			{
				head++;
			}
			else
			{
				tail--;
			}

		}

		return res;
	}
};